The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately: When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet to the next node (“NEXT_HOP”) along that route. The next node repeats this step and so forth.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated that induces creating a loop in the RIB or FIB. As an example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
One solution that has been proposed to the looping problem is described in co-pending patent application Ser. No. 10/340,371, filed 9 Jan. 2003, entitled “Method and Apparatus for Constructing a Backup Route in a Data Communications Network” of Kevin Miles et al., (“Miles et al.”), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein and discussed in more detail below. According to the solution put forward in Miles et al, where a repairing node detects failure of an adjacent component, then the repairing node computes a first set of nodes comprising the set of all nodes reachable according to its protocol other than nodes reachable by traversing the failed component. The repairing node then computes a second set of nodes comprising the set of all nodes from which a target node is reachable without traversing the failed component. The method then determines whether any intermediate nodes exist in the intersection between the first and second sets of nodes or a one-hop extension thereof and tunnels packets for the target node to a tunnel end point comprising a node in the intersection of the first and second sets of nodes.
The solution described in Miles et al can be further understood with reference to FIG. 1 which depicts an illustrative network diagram to which the solution is applied. A network includes a node P, reference numeral 10 to which nodes A, B, C and S, reference numerals 12, 14, 16, 18, are attached via respective links 20, 22, 24, 26. In the event of failure of node P, node S, acting as a repairing node, computes a first set of nodes reachable other than by the failed component, termed here node S's P-space, PS reference numeral 28. Node S also computes the nodes from which a target node B is reachable without traversing node P, termed here node B's Q-space BQ reference numeral 30. The repairing node, node S, then identifies that node E in PS and node F in QB, reference numerals 32, 34, are within one hop of each other via link 36. Node S then tunnels packets to node E via path 38, that is to say, node S encapsulates a packet and attaches, as a destination header, the address of node E. In order for the packet to traverse link 36, node S also adds a “direct forwarding” instruction to the encapsulated packet such that node E, upon decapsulating the packet forwards to node F irrespective of its next hop to node B. Once the packet reaches node F then, by definition, it will reach node B, via path 40 in node B's Q space QB.
An extension of the approach is described in co-pending patent application Ser. No. 10/976,076, filed 27th Oct. 2004, entitled “Method and Apparatus for Forwarding Data in a Data Communications Network” of George Swallow et al (“Swallow et al”) the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to this extension, the repairing node further calculates the Q-space of the other neighbors to the failed node, forming an “extended Q-space” and forwards the packet to a node in the intersection of P-space PS and the extended Q-space. Referring once again to FIG. 1, for example, the repairing node, node S identifies that the node E′, reference numeral 42 is reachable via a path 44 and lies in C's Q-space QC, reference numeral 45. The packet is then forwarded across Q-space QC via path 44 to a node F′, reference numeral 46, which also falls in B's Q-space QB and from which it is forwarded to node B via path 48.
The approach in Miles et al and Swallow et al can be implemented both for node and link failure. In the case of link failure, various solutions are proposed to avoid looping between the repairing node and neighbors of the node connected to the repairing node via the failed link and which may be implementing a conflicting repair strategy, that is to say between node S and nodes A, B and C in FIG. 1 in the event of failure of link 26.
One such solution is described in co-pending patent application Ser No. 10/346,051, filed 15th Jan. 2003, entitled “Method and Apparatus for Determining a Data Communication Network Repair Strategy” of Michael Shand et al (“Shand et al ”) the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to this approach a repairing node sends a probe packet along a repair path and, if the probe is returned, a loop is identified. A further solution is described in co-pending patent application Ser. No. 10/848,669, filed 18th May 2004, entitled “Method and Apparatus for Forwarding Data in a Data Communications Network” of Michael Shand et al (“Shand et al II”) the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to the approach described in Shand et all II a repair packet is marked as repaired to avoid looping.
Whilst such systems provide rapid network recovery in the event of a failed component the use of P and Q-space means that in many instances the repair path selected is not the shortest available repair path. Furthermore additional forwarding mechanisms such as directed forwarding are required in some instances. Yet further additional layers of encapsulation are required in certain instances, for instance in the case of use of extended Q-space or for instances such as multi-homed prefixes (MHP). Multiple encapsulation is undesirable for example because of the requirement for additional checksum calculations.
Many of these problems arise because, when a link or a router fails, only the neighbors of the failure are initially aware that the failure has occurred. According to the solution described above the failure is repaired by the routers that are the neighbors of the failure. These repairing routers have to steer packets to their destinations despite the fact that most other routers in the network are unaware of the nature and location of the failure.
A further known approach is described in “Fast Re-route using Alternative Shortest Paths” which is available at the time of writing on the file “draft-tian-ffr-alt-shortest-path-01.txt” in the directory “pub/id” of the domain “watersprings.org” on the World Wide Web. According to the approach described in this document a repairing node and each of its next hops calculate alternative shortest paths as repair paths around potential neighbor node failures by identifying a termination point for packets in the event of such failure and calculating alternate shortest paths by removing the failed node from the link state database. However this approach requires construction of explicit paths using, for example, source routing to encode the path in the packet itself